<?php

/**
 * 链表的实现
 * Class LinkedList
 */
class LinkedList
{
    private $dummyHead;
    private $size;

    /**
     * 初始化链表 null->null
     * LinkedList constructor.
     */
    public function __construct()
    {
        $this->dummyHead = new Node(null, null);
        $this->size = 0;
    }

    /**
     * 获取链表大小
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;
    }

    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;
    }

    /**
     * 在链表的第 index 位置添加元素
     * @param int $index
     * @param $e
     */
    public function add(int $index, $e): void
    {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        //将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点
        $prve->next = new Node($e, $prve->next);
        $this->size++;
    }

    /**
     * 向链表开头添加元素
     * @param $e
     */
    public function addFirst($e): void
    {
        $this->add(0, $e);
    }

    /**
     * 向链表末尾添加元素
     * @param $e
     */
    public function addLast($e): void
    {
        $this->add($this->size, $e);
    }

    /**
     * 获取链表第 index 位置元素
     * @param $index
     */
    public function get($index)
    {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }

        $node = $this->dummyHead;
        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }

        return $node->e;
    }

    /**
     * 获取链表第一个元素
     * @return mixed
     */
    public function getFirst()
    {
        return $this->get(0);
    }

    /**
     * 获取链表最后一个元素
     * @return mixed
     */
    public function getLast()
    {
        return $this->get($this->size - 1);
    }

    /**
     * 修改链表中第 index 位置元素值
     * @param $index
     * @param $e
     */
    public function update($index, $e)
    {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;

        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        $node->e = $e;
    }

    /**
     * 判断链表中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool
    {
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            if ($node->e == $e) {
                return true;
            }
        }
        return true;
    }

    /**
     * 删除链表中第 index 位置元素
     * @param $index
     */
    public function remove($index)
    {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        if ($this->size == 0) {
            echo "链表已经是空";
            exit;
        }

        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        $node = $prve->next;
        $prve->next = $node->next;

        $this->size--;
        return $node->e;
    }

    /**
     * 删除链表头元素
     */
    public function removeFirst()
    {
        return $this->remove(0);
    }

    /**
     * 删除链表末尾元素
     */
    public function removeLast()
    {
        return $this->remove($this->size - 1);
    }

    /**
     * 获取头结点信息
     * @return mixed
     */
    public function getHead()
    {
        return $this->dummyHead->next;
    }

    /**
     * 设置头
     * @param Node $head
     */
    public function setHead(Node $head)
    {
        $this->dummyHead->next = $head;
    }

    /**
     * 链表元素转化为字符串显示
     * @return string
     */
    public function toString(): string
    {
        $str = "";
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            $str .= $node->e . "->";
        }
        return $str . "null";
    }
}

class Node
{
    public $e;//节点元素
    public $next; //下个节点信息

    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next)
    {
        $this->e = $e;
        $this->next = $next;
    }
}

